package main

import "fmt"
import "github.com/the404/letcode/common"

// 验证二叉树，用中序遍历，然后每个数都要大于前一个数，主要是需要在递归方法中使用指针来传值
func main() {
	t1 := getbaseTree()

	arr := t1.InOrder_Traver()
	fmt.Println(arr)

	r := isValidBST(t1)
	fmt.Println(r)
}

func getbaseTree() *common.TreeNode {

	t5 := &common.TreeNode{6, nil, nil}
	t4 := &common.TreeNode{3, nil, nil}
	t3 := &common.TreeNode{4, t4, t5}
	t2 := &common.TreeNode{1, nil, nil}
	t1 := &common.TreeNode{5, t2, t3}

	//t3 := &common.TreeNode{3, nil, nil}
	//t2 := &common.TreeNode{1, nil, nil}
	//t1 := &common.TreeNode{2, t2, t3}

	//t2 := &common.TreeNode{1, nil, nil}
	//t1 := &common.TreeNode{1, t2, nil}
	return t1
}

func isValidBST(root *common.TreeNode) bool {
	isFirst := true
	lastVal := 0
	return InOrderTraver(root, &isFirst, &lastVal)
}

func InOrderTraver(root *common.TreeNode, isFirst *bool, lastVal *int) bool {
	flag := true
	if root == nil {
		return true
	}
	if root.Left != nil {
		flag = flag && InOrderTraver(root.Left, isFirst, lastVal)
	}

	if root != nil {
		if *isFirst {
			*isFirst = false
		} else if root.Val <= *lastVal {
			return false
		}
		*lastVal = root.Val
	}
	if root.Right != nil {
		flag = flag && InOrderTraver(root.Right, isFirst, lastVal)
	}
	return flag
}
